package offer.day19;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class No32First_PrintBinaryTreeFromTopToBottom {
    /*
     * 面试题32：从上到下打印二叉树    树的遍历 （按层次）
     * 题目一：不分行从上到下打印二叉树
     * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
     * 例如：输入8->6   8->10 这样的二叉树，打印出8，6，10，5，7，9，11
     * 		6->5   6->7
     * 		10->9  10->11
     *
     * 思路：从上到下打印二叉树时，借助一个队列进行操作
     * 从头节点开始进行打印，每次打印时，若是该节点有子节点，则都将该子节点放入队列的末尾；
     * 接下来取队列的头部元素，重复之前的打印操作，直到所有的节点都被打印出来
     *
     * */
    public static void main(String[] args) {
        No32First_PrintBinaryTreeFromTopToBottom p = new No32First_PrintBinaryTreeFromTopToBottom();
        BinaryTreeNode root = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(6);
        BinaryTreeNode two = new BinaryTreeNode(10);
        BinaryTreeNode three = new BinaryTreeNode(5);
        BinaryTreeNode four = new BinaryTreeNode(7);
        BinaryTreeNode five = new BinaryTreeNode(9);
        BinaryTreeNode six = new BinaryTreeNode(11);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = null;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        List<Integer> res = PrintBinaryTreeFromTopToBottom(root);
        System.out.println(res);
    }

    public static List<Integer> PrintBinaryTreeFromTopToBottom(BinaryTreeNode root){
        if(root==null) return new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            BinaryTreeNode tmp=queue.poll();
            list.add(tmp.val);
            if(tmp.left!=null){
                queue.add(tmp.left);
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
            }
        }
        return list;
    }
}
